// 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

// 要求返回这个链表的深拷贝。 

 

// 示例：



// 输入：
// {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

// 解释：
// 节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
// 节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
 

// 提示：

// 你必须返回给定头的拷贝作为对克隆列表的引用。

#include <unordered_map>
#include <queue>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

/* 深度优先遍历
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (nullptr == head) {
            return nullptr;
        }
        if (hash.find(head) != hash.end()) {
            return hash[head];
        }
        Node* node = new Node(head->val);
        hash[head] = node;
        node->next = copyRandomList(head->next);
        node->random = copyRandomList(head->random);
        return node;
    }
private:
    unordered_map<Node*, Node*> hash{}; // 原节点与对应的clone节点
};

/* 两次遍历，分别考虑next和random
把原节点和clone节点的对应关系存在hash表中
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (nullptr == head) {
            return nullptr;
        }
        unordered_map<Node*, Node*> hash{}; // 原节点与对应的clone节点
        Node* newHead = new Node(head->val);
        hash[head] = newHead;
        Node* newListPre = newHead;
        Node* cur = head->next;
        while (cur) {
            Node* t = new Node(cur->val);
            hash[cur] = t;
            newListPre->next = t;
            newListPre = newListPre->next;
            cur = cur->next;
        }
        newListPre = newHead;
        cur = head;
        while (newListPre) {
            newListPre->random = hash[cur->random];
            newListPre = newListPre->next;
            cur = cur->next;
        }
        return newHead;
    }
};

/* 在原节点之后复制节点，最后再分离
1. 在原链表的每个节点后面拷贝出一个新的节点
2. 依次给新的节点的随机指针赋值，而且这个赋值非常容易 cur->next->random = cur->random->next
3. 断开链表可得到深度拷贝后的新链表
时间复杂度：O(n)
空间复杂度：O(1)
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (nullptr == head) {
            return nullptr;
        }
        Node* cur = head;
        while (cur) {
            Node* node = new Node(cur->val);
            node->next = cur->next;
            cur->next = node;
            cur = node->next;
        }
        cur = head;
        while (cur) {
            if (nullptr != cur->random) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        cur = head;
        Node* res = cur->next;
        while (cur) {
            Node* t = cur->next;
            cur->next = t->next;
            if (t->next) {
                t->next = t->next->next;
            }
            cur = cur->next;
        }
        return res;
    }
};
